package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.Scanner;

/*
有一个大小为 N*M 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼？（八连通指的是下图中相对 W 的*的部分）
    ***
    *W*
    ***
限制条件
 N, M ≤ 100
 样例:
	输入
		N=10, M=12
	园子如下图（'W'表示积水，'.'表示没有积水）
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

	输出
		3
 */
public class hDFS_水洼数目by深搜思想 {
	public static void main(String[] args) {
		hDFS_水洼数目by深搜思想 test = new hDFS_水洼数目by深搜思想();
		int res1 = test.useDFS_PuddlesOfWater();
		System.out.println(res1);		
//		test.test();
	}
	
	/**
	 * 前置方法
	 * 不用回溯
	 * @return
	 */
	public int useDFS_PuddlesOfWater() {
		Scanner scanner = new Scanner(System.in);
		int Row = scanner.nextInt();
		int Col = scanner.nextInt();
		char[][] arr = new char[Row][Col];
		int count = 0;
		for (int i = 0; i < Row; i++) {
			arr[i] = scanner.next().toCharArray();
		}
		//下面的双重循环，是全局角度，寻找水洼
		for (int i = 0; i < Row; i++) {
			for (int j = 0; j < Col; j++) {
				if (arr[i][j] == 'W') {//发现水洼的一部分，开始“递归的方式”执行清除水洼
					DFS_PuddlesOfWater(arr, i, j);
					count++;//只要进入了if，并且if中的DFS执行完了，就代表着一滩水洼清除完毕；就意味着矩阵中存在一个水洼
				}
			}
		}
		return count;
	}
	
	/**
	 * 递归形式
	 * 不需要写出口了，因为8方向没有W的话，这个方法返回值是void
	 * 会直接结束方法(也就是默认return;)
	 * @param arr
	 * @param row
	 * @param col
	 */
	public void DFS_PuddlesOfWater(char[][] arr, int row, int col) {
		arr[row][col] = '.';//传进来的arr[row][col]，一定是'W'，所以首先把W消除
		//下面的双重循环，是以arr[row][col]为[0,0],对周围8各方位进行判断，判断是否有‘W’
		for (int x = -1; x < 2; x++) {//-1 <= x <= 1
			for (int y = -1; y < 2; y++) {//-1 <= y <= 1
				if (x == 0 && y == 0) {//这个if用来跳过自身arr[row][col]
					continue;
				}
				if (row + x >= 0 && row + x < arr.length && col + y >= 0 && col + y <arr[0].length) {//这个if用来防止，指针越界
					if (arr[row + x][col + y] == 'W') {//在8方位中发现'W'，递归尝试
						DFS_PuddlesOfWater(arr, row + x, col + y);
					}
				}
			}
		}
	}
	
	public void test() {
		Scanner scanner = new Scanner(System.in);
		int Row = scanner.nextInt();
		int Col = scanner.nextInt();
		char[][] arr = new char[Row][Col];
		int count = 0;
		for (int i = 0; i < Row; i++) {
//			arr[i] = scanner.nextLine().toCharArray();
			arr[i] = scanner.next().toCharArray();
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.println(new String(arr[i]));
		}
	}
}
